package com.aqie.medium.sort;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;

/**
 * 215 数组中第K个最大元素(元素可以有重复)
 */
public class FindKthLargest {
    /**
     * 1, 分治
     * @param arr
     * @param k
     * @return
     */
    public int findKthLargest(int[] arr, int k) {
        return 0;
    }

    /**
     * 2, 最大堆 O(Nlogk) 73ms
     * @param arr
     * @param k
     * @return
     */
    public int findKthLargest2(int[] arr, int k) {
        // init heap 'the smallest element first'
        PriorityQueue<Integer> heap =
                new PriorityQueue<Integer>((n1, n2) -> n1 - n2);

        // keep k largest elements in the heap
        for (int n: arr) {
            heap.add(n);
            if (heap.size() > k)
                heap.poll();
        }

        // output
        return heap.poll();

    }

    /**
     * 3, O(N) 桶排序
     * @param arr
     * @param k
     * @return
     */
    public int findKthLargest3(int[] arr, int k) {
        int max = Integer.MIN_VALUE,min = Integer.MAX_VALUE;
        for(int i : arr){
            max = Math.max(max,i);
            min = Math.min(min,i);
        }
        int n = max - min;
        int[] bucket = new int[n + 1];
        for(int i = 0;i < arr.length;i++){
            int tmp = arr[i] - min;
            bucket[tmp]++;
        }
        for(int i = n;i >= 0;i--){
            if(bucket[i] > 0)
                k -= bucket[i];
            if(k <= 0)
                return i + min;
        }
        return 0;
    }


    /**
     * 4, 桶排序 4ms
     * @param arr
     * @param k
     * @return
     */
    public int findKthLargest4(int[] arr, int k) {
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        for(int num:arr){
            max=Math.max(max,num);
            min=Math.min(min,num);
        }
        int[] bucket=new int [max-min+1];
        for(int num:arr){
            bucket[num-min]++;
        }
        int count=0;
        for(int i=bucket.length-1;i>=0;i--){
            count+=bucket[i];
            if(count>=k)    return min+i;
        }
        return -1;
    }

    /**
     * 5,36ms
     * @param arr
     * @param k
     * @return
     */
    public int findKthLargest5(int[] arr, int k) {
        return find(arr, k, 0, arr.length - 1);
    }
    private static int find(int arr[], int k, int p, int q) {
        int m = partition(arr, p, q);
        if (m + k == arr.length) {
            return arr[m];
        } else if (m + k  < arr.length) {
            return find(arr, k, m + 1, q);
        }else{
            return find(arr, k, p, m - 1);
        }
    }
    private static int partition(int arr[], int p, int q) {
        int k = p;
        while (p < q) {
            if(arr[p]<arr[q])
                swap(arr, k++, p);
            p++;
        }
        swap(arr, k, q);
        return k;
    }

    private static void swap(int arr[], int p, int q) {
        int temp = arr[p];
        arr[p] = arr[q];
        arr[q] = temp;
    }

    /**
     * 6. 排序, 第K大 不受重复元素影响   7ms
     * @param arr
     * @param k
     * @return
     *
     */
    public static int findKthLargest6(int[] arr, int k) {
        Arrays.sort( arr );
        return arr[ arr.length - k ];
    }


    /**
     * 7,  Hoare选择算法。快速选择算法 O（n） 4ms
     */
    int [] arr;

    public void swap(int a, int b) {
        int tmp = this.arr[a];
        this.arr[a] = this.arr[b];
        this.arr[b] = tmp;
    }


    public int partition(int left, int right, int pivot_index) {
        int pivot = this.arr[pivot_index];
        // 1. move pivot to end
        swap(pivot_index, right);
        int store_index = left;

        // 2. move all smaller elements to the left
        for (int i = left; i <= right; i++) {
            if (this.arr[i] < pivot) {
                swap(store_index, i);
                store_index++;
            }
        }

        // 3. move pivot to its final place
        swap(store_index, right);

        return store_index;
    }

    public int quickselect(int left, int right, int k_smallest) {
    /*
    Returns the k-th smallest element of list within left..right.
    */

        if (left == right) // If the list contains only one element,
            return this.arr[left];  // return that element

        // select a random pivot_index
        Random random_num = new Random();
        int pivot_index = left + random_num.nextInt(right - left);

        pivot_index = partition(left, right, pivot_index);

        // the pivot is on (N - k)th smallest position
        if (k_smallest == pivot_index)
            return this.arr[k_smallest];
            // go left side
        else if (k_smallest < pivot_index)
            return quickselect(left, pivot_index - 1, k_smallest);
        // go right side
        return quickselect(pivot_index + 1, right, k_smallest);
    }

    public int findKthLargest7(int[] arr, int k) {
        this.arr = arr;
        int size = arr.length;
        // kth largest is (N - k)th smallest
        return quickselect(0, size - 1, size - k);
    }


    /**
     * 8. 快排  48ms
     * @param arr
     * @param k
     * @return
     */
    public int findKthLargest8(int[] arr, int k) {
        if(arr==null || arr.length==0 || k>arr.length) return -1;
        int n = arr.length-k;
        int l = 0, r= arr.length-1;
        while(l < r){
            int index = partition2(arr,l,r);
            if(index == n) return arr[n];
            if(index > n) r = index - 1;
            else l = index + 1;
        }
        return arr[n];
    }
    private int partition2(int[] arr, int l, int r){
        int k = arr[l];
        while(l < r){
            while(l < r && arr[r] >= k) r--;
            arr[l] = arr[r];
            while(l < r && arr[l] <= k) l++;
            arr[r] = arr[l];
        }
        arr[l] = k;
        return l;
    }

    public static void main(String[] args) {
        int[] arr = {3,2,2,3,1,2,4,5,5,6};
        int  k = 4;
        System.out.println(findKthLargest6(arr, k));

    }
}
